package com.lisp.algorithm.sort;

import java.util.Arrays;

import com.lisp.algorithm.util.SortUtil;

public class RadixSort {
    
    public static void main(String[] args) {
        SortUtil.test(RadixSort::radixSort);
    }

    public static void radixSort(int a[]) {
        // int bits = 8;
        for(int round=0; round<4; round++) {
            countingSort(a, round);
        }
    }
    
    public static void countingSort(int a[], int round) {

        int counting[] = new int[256];
        
        for(int i=0; i<a.length; i++) {
            int maskValue = (a[i] >> (round*8)) & 0xff;
            counting[maskValue]++;
        }
        
        for(int i=1; i<counting.length; i++) {
            counting[i] = counting[i] + counting[i-1];
        }
        
        int tmp[] = Arrays.copyOf(a, a.length);
        for(int i=tmp.length-1; i>=0; i--) {
            int maskValue = (tmp[i] >> (round*8)) & 0xff;
            a[counting[maskValue]-1] = tmp[i];
            counting[maskValue]--;
        }
    }
}
